{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Graph Theory in Python: Routing example\n",
    "\n",
    "## Try me\n",
    "[![Open In Colab](../../_static/colabs_badge.png)](https://colab.research.google.com/github/ffraile/operations-research-notebooks/blob/main/docs/source/MIP/tutorials/Routing%20example.ipynb)[![Binder](../../_static/binder_badge.png)](https://mybinder.org/v2/gh/ffraile/operations-research-notebooks/main?labpath=docs%2Fsource%2FMIP%2Ftutorials%2FRouting%20example.ipynb)\n",
    "\n",
    "## Description\n",
    "In this notebook, you will learn how to solve network problems using Python. For the set-up, we will use a map of the city of Valencia, and calculate the shortest distance between two points using the actual street map of the city.\n",
    "We will use the following libraries: \n",
    "\n",
    "- [Networkx](https://networkx.org/): This Python library implements a lot of network theory utils and algorithms and is the main library used in the problems. \n",
    "\n",
    "- [Osmnx](https://osmnx.readthedocs.io/en/stable/): This library allows us to create a graph from an Open Street Maps query (similar to what you would use to find a place in Google Maps).\n",
    "\n",
    "Additionally, we will use the following libraries to render the maps:\n",
    "\n",
    "- [Folium](https://python-visualization.github.io/folium/index.html): This library allows us to render the maps in our Notebooks\n",
    "\n",
    "Remember you must **Trust** the notebook to test it.\n",
    "In Colabs, Run the following cell to install the libraries:"
   ]
  },
  {
   "cell_type": "code",
   "source": [
    "!pip install networkx[default,extra]\n",
    "!apt-get -qq install -y libspatialindex-dev\n",
    "!pip install osmnx\n",
    "!pip install folium\n",
    "!pip install python-igraph\n",
    "!pip install mapclassify"
   ],
   "metadata": {
    "collapsed": false,
    "pycharm": {
     "is_executing": true
    }
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Network creation\n",
    "First we need to create the map:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "import networkx as nx\n",
    "import osmnx as ox\n",
    "from IPython.display import IFrame\n",
    "%matplotlib inline\n",
    "\n",
    "\n",
    "# Get the map of Valencia\n",
    "G_nx = ox.graph_from_place('Valencia, VC, Spain', network_type='drive')\n",
    "\n",
    "print(\"The streets of Valencia can be modeled with a graph of size: \" + str(G_nx.size()))"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Code Explanation\n",
    "We have created a graph that represents the streets of Valencia, Spain, using the function `ox.graph_from_place`. The function takes as input a place name, and returns a graph of the streets in that place. The parameter `network_type` specifies the type of streets that we want to include in the graph. In this case, we are only interested in streets that can be used by cars. Other possible values are `walk` (pedestrian streets), `bike` (streets that can be used by bikes), `drive_service` (service roads), `all` (all the streets in the place).\n",
    "\n",
    "Now, the object G_nx is a graph of the city, we do some adaptations that will allow us to work with the map more easily:"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "pycharm": {
     "name": "#%% \n"
    }
   },
   "source": [
    "# convert osmids IDs to a list\n",
    "osmids = list(G_nx.nodes)\n",
    "\n",
    "# Relabel the nodes with integers. This facilitates handling the tree\n",
    "G_nx = nx.relabel.convert_node_labels_to_integers(G_nx)\n",
    "\n",
    "# give each node its original osmid as attribute, since we relabeled them\n",
    "osmid_values = {k:v for k, v in zip(G_nx.nodes, osmids)}\n",
    "nx.set_node_attributes(G_nx, osmid_values, 'osmid')\n",
    "\n"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Rendering the map\n",
    "Let us now plot the map in an interactive component:\n"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {
    "scrolled": true
   },
   "source": [
    "ox.graph_to_gdfs(G_nx, nodes=False).explore()\n"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Code explanation\n",
    "The function `ox.graph_to_gdfs` converts the graph to a GeoDataFrame, which is a data structure that allows us to plot the graph in an interactive map. The parameter `nodes=False` indicates that we are not interested in plotting the nodes of the graph (only the edges).\n",
    "Any GeoDataframe can be plotted using the function `explore()`. As we will see in the next section, we can also explore routes in the map using this function."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Shortest path\n",
    "Let us now define a function that uses this map to calculate the shortest path. \n"
   ]
  },
  {
   "cell_type": "code",
   "metadata": {},
   "source": [
    "def get_route(source, destination):\n",
    "    \"\"\"\n",
    "    Given two coordinates (source and destination) calculate the shortest path between the closest nodes to the source and\n",
    "    the closest node to the destination.\n",
    "     A point is a tuple of two double values specifying latitude and longitude (e.g. point_1 = (39.464060144309364,\n",
    "     -0.3624288516715025)).\n",
    "\n",
    "    Args:\n",
    "        source - A tuple containing latitude and longitude values of the source point.\n",
    "        destination - A tuple containing latitude and longitude values of the source point.\n",
    "\n",
    "    Returns: \n",
    "        route: The shortest path along the map\n",
    "        distance: the minimum distance in meters (summation of great-circle distance between nodes in the shortest path)\n",
    "    \"\"\"\n",
    "    # Get the nearest node to source\n",
    "    node_1 = ox.distance.nearest_nodes(G_nx, X=source[0], Y=source[1])\n",
    "\n",
    "    # Get the nearest node to destination\n",
    "    node_2 = ox.distance.nearest_nodes(G_nx, X=destination[0], Y=destination[1])\n",
    "\n",
    "    # Get the shortest path between source and destination nodes\n",
    "    route = ox.shortest_path(G_nx, node_1, node_2)\n",
    "\n",
    "    # Return the route and the nearest nodes\n",
    "\n",
    "    return route, [node_1, node_2]"
   ],
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Code Explanation\n",
    "The function above uses the following functions from the libraries:\n",
    "\n",
    "- `ox.distance.nearest_nodes(G_nx, X=source[0], Y=source[1])`: This function returns the nearest node to a given point. The point is specified by its latitude and longitude.\n",
    "- `ox.shortest_path(G_nx, node_1, node_2)`: This function returns the shortest path between two nodes in the graph.\n",
    "\n",
    "\n",
    "The function basically uses the previous functions to first find the nearest nodes to the source and destination points, and then calculates the shortest path between them. Finally, it returns the shortest path and the nearest nodes of the graph which are closer to the provided coordinates.\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test between two points\n",
    "\n",
    " Let us test the function!. From Google Maps, it is very easy to get the coordinates of a point. Just right-click on the map, and it will show the coordinates. After, you can hover over the coordinates and left click to copy the coordinates to your clipboard. Now, if you paste in Google Colabs, you will get the coordinates of the point.\n",
    "\n",
    "![ Coordinates](./img/getting_coordinates_from_google_maps.png){width=50%}\n",
    "\n",
    "Note that the coordinates are in the form (latitude, longitude). However, the function `get_route` expects the coordinates in the form (longitude, latitude). Therefore, we need to invert the coordinates before passing them to the function.\n",
    "\n",
    "Here is an example of two points in Valencia:\n",
    "\n",
    "- [EDEM](https://edem.eu/): Coordinates (-0.3288013882525529, 39.46211739713285)\n",
    "- [CIGIP Research Center @ UPV](https://cigip.webs.upv.es/index.php/en/): Coordinates (-0.3344765250611888, 39.46211739713285)"
   ]
  },
  {
   "cell_type": "code",
   "source": [
    "edem = (-0.3288013882525529, 39.46211739713285)\n",
    "cigip = (-0.3346191716152525, 39.47696577364303)\n",
    "\n",
    "route, nodes = get_route(edem, cigip)\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Converting to GeoDataFrame\n",
    "Now, we can convert the route to a GeoDataFrame, which is a dataframe containing the information of the route. This will allow us for instance to calculate the total distance or to plot the route in a map.\n",
    "The function used to convert the route to a GeoDataFrame is `ox.routing.route_to_gdf`. The function takes as input the graph, the route and the attribute that we want to use to calculate the distance. In this case, we are using the attribute `length`, which is the length of the street in meters."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "source": [
    "route_edges = ox.routing.route_to_gdf(G_nx, route, weight=\"length\")\n",
    "display(route_edges.head())"
   ],
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Calculating the distance\n",
    "Now, we can calculate the distance of the route by summing the length of the streets in the route. The length of the streets is stored in the column `length` of the GeoDataFrame. Therefore, we can use the function `sum` to calculate the total distance."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "source": [
    "total_distance = sum(route_edges[\"length\"])\n",
    "print(\"The total distance between the two points is: \" + str(total_distance) + \" meters\")"
   ],
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Exploring the route\n",
    "Finally, we can plot the route in a map using the function `explore` of the GeoDataFrame. The function takes as input the map where we want to plot the route. We can use the argument `color` to specify the color of the route, the argument `style_kwds` to define style properties, and the argument `m` to specify the map where we want to plot the route. If we do not specify the map, the function will create a new map. In the example below we set the weight of the route to 5 to plot it in a thicker line."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "source": [
    "route_edges.explore( style_kwds={\"weight\": 5})"
   ],
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Getting the routes of a distribution network\n",
    "We can use the function `get_route`and the information contained in Geo Dataframes to get the routes of a distribution network. For instance, let us calculate the routes for a distribution network with two sources and two destinations in Valencia."
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "source": [
    "sources = [\n",
    "    {\n",
    "        \"id\": 1,\n",
    "        \"coordinates\": (-0.3783881019008758, 39.47875115874353)},\n",
    "    {\n",
    "        \"id\": 2,\n",
    "        \"coordinates\": (-0.3929897392129934, 39.4817119703732)\n",
    "    }]\n",
    "\n",
    "destinations = [\n",
    "    {\n",
    "        \"id\": 1,\n",
    "        \"coordinates\": (-0.3346191716152525, 39.47696577364303)},\n",
    "    {\n",
    "        \"id\": 2,\n",
    "        \"coordinates\": (-0.3288013882525529, 39.46211739713285)\n",
    "    }]\n",
    "\n",
    "# Init the routes and distances\n",
    "distances = []\n",
    "\n",
    "routes = []\n",
    "\n",
    "# Iterate over the sources and destinations\n",
    "for source in sources:\n",
    "    for destination in destinations:\n",
    "        route, nodes = get_route(source[\"coordinates\"], destination[\"coordinates\"])\n",
    "        route_gdf = ox.routing.route_to_gdf(G_nx, route, weight=\"length\")\n",
    "        routes.append(\n",
    "            {\n",
    "                \"source\": source[\"id\"],\n",
    "                \"destination\": destination[\"id\"],\n",
    "                \"route\": route_gdf\n",
    "            }\n",
    "        )\n",
    "        distance = sum(route_gdf[\"length\"])\n",
    "        distances.append(\n",
    "            {\n",
    "                \"source\": source[\"id\"],\n",
    "                \"destination\": destination[\"id\"],\n",
    "                \"distance\": distance\n",
    "            }\n",
    "        )\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "### Code Explanation\n",
    "In the code above, we have defined two dictionaries with the information of sources and destinations, and then we have iterated over them to calculate the routes and distances, using the `get_route` function defined before. We have stored the different routes in a list of GeoDataFrames, and the distances in a list of dictionaries. The dictionaries contain the information of the source, destination and distance of each route.\n",
    "\n",
    "Now, we can for instance display a dataframe with the distances:\n"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "source": [
    "import pandas as pd\n",
    "pd.DataFrame(distances)\n"
   ],
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "We can also plot the routes using the following script:"
   ],
   "metadata": {
    "collapsed": false
   }
  },
  {
   "cell_type": "code",
   "source": [
    "# Define a color map so that the routes have different colors depending on the source\n",
    "# we use source ids as keys and colors as values. The colors are semi-transparent so that we can see the routes even if they overlap\n",
    "color_map = {\n",
    "    1: \"#ff000055\",\n",
    "    2: \"#0000ff55\"\n",
    "}\n",
    "\n",
    "# Add the first route to a map\n",
    "m = routes[0][\"route\"].explore(color=color_map[routes[0][\"source\"]],  style_kwds={\"weight\": 5})\n",
    "\n",
    "# Add the rest of the routes to the map\n",
    "for route in routes[1:]:\n",
    "    route[\"route\"].explore(color=color_map[route[\"source\"]],  style_kwds={\"weight\": 5}, m=m)\n",
    "\n",
    "# Display the map\n",
    "m"
   ],
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "execution_count": null
  },
  {
   "cell_type": "markdown",
   "source": [
    "## Analysis questions\n",
    "1. Try the scripts with other points in the map. What is the shortest path between them?\n",
    "2. What are the main limitations of this approach? How could we improve it?\n",
    "3. Try to get the distance using a mapping application (e.g. Google Maps). What is the difference between the distance calculated by the script and the distance calculated by the application? Why?\n",
    "4. Ask an AI assistant to describe the concept of Manhattan distance to you. Calculate the Manhattan distance between the two points. What is the difference between the distance calculated by the script and the distance calculated by the application? Why? Could you use the Manhattan distance to improve the script?\n"
   ],
   "metadata": {
    "collapsed": false
   }
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.1"
  },
  "pycharm": {
   "stem_cell": {
    "cell_type": "raw",
    "source": [],
    "metadata": {
     "collapsed": false
    }
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}